package ch09_11;

import java.util.*;

public class Solution {
	private static String ONE = "1", ZERO = "0";
	private static Character AND = '&', OR = '|', XOR = '^';

	public static long count_1(String expr, boolean expected) {
		if (expr.length() == 1) {
			if (expr.equals(ONE)) {
				if (expected)
					return 1;
				return 0;
			} else if (expr.equals(ZERO)) {
				if (expected)
					return 0;
				return 1;
			}
		}
		long count = 0;

		for (int i = 1; i < expr.length(); i += 2) {
			char operator = expr.charAt(i);
			long leftFalse = count_1(expr.substring(0, i), false);
			long leftTrue = count_1(expr.substring(0, i), true);
			long rightFalse = count_1(expr.substring(i + 1), false);
			long rightTrue = count_1(expr.substring(i + 1), true);
			switch (operator) {
			/**
			 * Good Question. "case expressions must be constant expressions.
			 */
			case '&':
				if (expected == false) {
					count += leftFalse * (rightFalse + rightTrue);
					count += leftTrue * rightFalse;
				} else {
					count += leftTrue * rightTrue;
				}
				break;
			case '|':
				if (expected == true) {
					count += leftTrue * (rightFalse + rightTrue);
					count += leftFalse * rightTrue;
				} else {
					count += leftFalse * rightFalse;
				}
				break;
			case '^':
				if (expected == true) {
					count += leftTrue * rightFalse;
					count += leftFalse * rightTrue;
				} else {
					count += leftTrue * rightTrue;
					count += leftFalse * rightFalse;
				}
				break;
			}
		}
		return count;
	}

	public static long count_memoization(String expr, boolean desired) {
		Map<Boolean, Map<String, Long>> memo = new HashMap<Boolean, Map<String, Long>>();
		Map<String, Long> m1 = new HashMap<String, Long>();
		Map<String, Long> m2 = new HashMap<String, Long>();
		memo.put(true, m1);
		memo.put(false, m2);
		return count_memoization(expr, desired, memo);
	}

	private static long count_memoization(String expr, boolean desired,
			Map<Boolean, Map<String, Long>> memo) {
		Map<String, Long> map = memo.get(desired);
		if (map.containsKey(expr)) {
			return map.get(expr);
		}
		long count = 0;
		if (expr.length() == 1) {
			if (expr.equals(ONE)) {
				if (desired == true) {
					count = 1;
				} else {
					count = 0;
				}
			} else {
				if (desired == true) {
					count = 0;
				} else {
					count = 1;
				}
			}
			map.put(expr, count);
			return count;
		}

		for (int i = 1; i < expr.length(); i += 2) {
			long leftFalse = count_1(expr.substring(0, i), false);
			long leftTrue = count_1(expr.substring(0, i), true);
			long rightFalse = count_1(expr.substring(i + 1), false);
			long rightTrue = count_1(expr.substring(i + 1), true);
			char operator = expr.charAt(i);

			switch (operator) {
			/**
			 * Good Question. "case expressions must be constant expressions.
			 */
			case '&':
				if (desired == false) {
					count += leftFalse * (rightFalse + rightTrue);
					count += leftTrue * rightFalse;
				} else {
					count += leftTrue * rightTrue;
				}
				break;
			case '|':
				if (desired == true) {
					count += leftTrue * (rightFalse + rightTrue);
					count += leftFalse * rightTrue;
				} else {
					count += leftFalse * rightFalse;
				}
				break;
			case '^':
				if (desired == true) {
					count += leftTrue * rightFalse;
					count += leftFalse * rightTrue;
				} else {
					count += leftTrue * rightTrue;
					count += leftFalse * rightFalse;
				}
				break;
			}
		}
		map.put(expr, count);
		return count;
	}
	
//	public static long count_best()

	public static void main(String... args) {
		String expr = "1^0|0|1^0&1&0|1^0^1&0|1|0";
		boolean desired = true;
		long t1 = System.currentTimeMillis();
//		long result1 = count_1(expr, desired);
		long t2 = System.currentTimeMillis();
//		System.out.println(result1 + ", \t " + (t2 - t1) + " ms");
		long result2 = count_memoization(expr, desired);
		long t3 = System.currentTimeMillis();
		System.out.println(result2 + ", \t " + (t3 - t2) + " ms");
	}
}